//https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=13&tqId=23458&ru=%2Fpractice%2F1624bc35a45c42c0bc17d17fa0cba788&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//题目：重要！！！


#include <iostream>
#include <vector>
#include <climits>
#include <stack>
#include <queue>
#include <deque>
using namespace std;


// 滑动窗口的最大值
class Solution {
  public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {

        std::vector<int >maxInWindows;
        if (num.size() >= size && size >= 1) {

            std::deque<int> index;   // 存放索引号,存放第一个最大值。
            for (unsigned int i = 0; i < size; ++i) {
                while (!index.empty() && num[i] >= num[index.back()]) {
                    index.pop_back();
                }
                index.push_back(i);
            }
            maxInWindows.push_back(num[index.front()]);

            for (unsigned int i = size; i < num.size(); ++i) {
                // 如果值是大于deque里面的最大值的，那么直接删掉。
                while (!index.empty() && num[i] >= num[index.back()]) {
                    index.pop_back();
                }
                //如果是小，那么就先留着，这样队列的头部始终拿着最大值。
                if (!index.empty() && index.front() <= (int)(i - size)) {
                    index.pop_front();
                }
                index.push_back(i);
                maxInWindows.push_back(num[index.front()]);
            }
            
        }
        return maxInWindows;
    }
};